package site.wanjiahao.sort.uncompare;

import site.wanjiahao.sort.Sort;

import java.util.ArrayList;
import java.util.List;

public class BucketSort extends Sort<Double> {


    @Override
    protected void sort() {
        // 分配array.length 的空间
        List[] buckets = new List[array.length];
        // 存入桶数据
        for (Double aDouble : array) {
            int bucketIndex = (int) (aDouble * array.length);
            List bucket = buckets[bucketIndex];
            if (bucket == null) {
                bucket = new ArrayList();
                buckets[bucketIndex] = bucket;
            }
            bucket.add(aDouble);
        }

        // 取出桶中数据，对每一个桶进行排序
        int n = 0;
        for (List bucket: buckets) {
            if (bucket == null) continue;
            bucket.sort(null);
            // 存入原来数据
            for (Object o : bucket) {
                array[n++] = (Double) o;
            }
        }
    }
}
